package com.cat.dataStructure;

import java.util.ArrayDeque;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/asteroid-collision/description/
 * @create 2025/9/9 10:37
 * @since JDK17
 */

public class Solution66 {
    public int[] asteroidCollision(int[] asteroids) {
        int n = asteroids.length;
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (stack.isEmpty() || !(stack.peek() > 0 && asteroids[i] < 0)) {   // 不会相撞
                stack.push(asteroids[i]);
            } else {    // 相撞
                boolean flag = false;
                while (!stack.isEmpty() && stack.peek() > 0 && asteroids[i] < 0) {
                    int a = stack.pop();
                    if (Math.abs(a) > Math.abs(asteroids[i])) {
                        flag = true;
                        stack.push(a);
                        break;
                    }
                    if (Math.abs(a) == Math.abs(asteroids[i])) {    // 相等了
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    stack.push(asteroids[i]);
                }
            }
        }
        int[] ans = new int[stack.size()];
        for (int i = stack.size() - 1; i >= 0; i--) {
            ans[i] = stack.pop();
        }
        return ans;
    }
}